1. Field of the Invention
The present invention involves a graphics processing system for creating a pixel map of an image from data defining image area boundaries for display on display means.
2. Description of the Related Art including imformation disclosed under 37 CFR 1.97 - 1.99
Graphics processing systems can take many forms. There are systems which are particularly dedicated to graphics such as those used in computer aided design. However, many general purpose and other processing systems also provide graphics functions. For example, many text processing systems are provided with facilities for creating charts such as histograms, pie charts, and special images. The use of the term "graphics processing system" as used herein is consequently intended to be interpreted generally to include such systems, that is any system in which information can be represented pictorially rather than or as well as alphanumerically and one or more areas making up an image or pictuure for display can be defined in terms of the boundaries of those areas.
By an "area" is meant a plane figure whose outline or boundary consists of lines and/or curves. Areas can be convex, non-convex and can contain holes. In general terms, therefore, an "area" means a general form of boundary, possibly with holes and self intersections. A polygon is a particular form of area which has a boundary formed from straight lines. An area can be defined in a graphics system in many ways. Generally, however, an area will be defined in terms of line or curve segments. In the case of a polygon, the definitions of the vertices and the straight line segments joining the vertices suffice.
Areas will often be filled with color, patterns and/or shading. In general, this is done to make an image more effective. For example, filling can be used to enable areas to be more readily distinguished (e.g., in bar and pie charts), for highlighting areas of particular importance, or to make images of a three dimensional object more realistic (e.g., in modelling and/or computer aided design systems). The shading itself can , for example, be performed using Gouraud shading. This provides for the smooth shading of flat areas of an image. If an area for display is defined in terms of its edges, it is necessary to determine which points on the final image fall within the area in order that the appropriate locations in the image buffer may be set so as to give the corresponding pixels in the image the correct color and/or intensity.
Most common display devices used today are based on a raster scanning principle (e.g., raster-scanned cathode ray tubes). In order to drive these devices it is necessary to generate the individual picture elements (pixels) making up the image in time with the scanning of the image. Conveniently, this can be done using a screen or image buffer to hold a bit map of the image to be displayed on the display screen at any one time. This creates problems, however, where the areas making up an image are defined in terms of their edges as it is then necessary to process the definitions of the areas to identify the individual image pixels which are occupied by each area and accordingly the coloring and/or shading appropriate for those individual pixels. General aspects of these problems are discussed in Chapter II of foley and Van Dam's book "Fundamentals of Interactive Computer Graphics" (see especially pages 456-461), published By Addison-Wesley in 1982.
In accordance with one prior technique for shading an area, another buffer containing an additional image map called a spare bit plane is provided in addition to the image buffer and each area forming part of the image is separately processed using this additional map. Before each area is processed, the pixel locations in the additional map need to be reset. Then, the edges of an area are computed and locations are set in the additional map. When all the edges of an area have been written into the additional map buffer it is then possible to set individual pixel locations in the image buffer by scanning the additional map and alternately starting filling and stopping filling in corresponding locations in the image buffer map on crossing a set location in the additional map. Once the infilling has been completed, the next area can be treated using the additional map. A technique of this type is described by Ackland and West in their article entitled "The Edge Flag Algorithm - A Fill Method for Raster Scan Displays" which was published in IEEE Transactions in Computers, Vol. C30, pp. 41 to 48 in 1981.